package com.sheng.leetcode.year2023.month11.day21;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/11/21
 * <p>
 * 2216. 美化数组的最少删除数<p>
 * <p>
 * 给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：<p>
 * nums.length 为偶数<p>
 * 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立<p>
 * 注意，空数组同样认为是美丽数组。<p>
 * 你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。<p>
 * 返回使 nums 变为美丽数组所需删除的 最少 元素数目。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [1,1,2,3,5]<p>
 * 输出：1<p>
 * 解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [1,1,2,2,3,3]<p>
 * 输出：2<p>
 * 解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 10^5<p>
 * 0 <= nums[i] <= 10^5<p>
 */
public class LeetCode2216 {

    @Test
    public void test01() {
//        int[] nums = {1, 1, 2, 3, 5};
        int[] nums = {1, 1, 2, 2, 3, 3};
        System.out.println(new Solution().minDeletion(nums));
    }
}

class Solution {
    public int minDeletion(int[] nums) {
        // 要求数组长度为偶数，并且每个偶数索引对应的元素与后一个元素不相等
        // 假设第 0 个和第 1 个元素相等，那么要求在两个元素中删除一个，然后比较第 0 个和第 2 个元素
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i != n - 1) {
                int m = i + 1;
                // 遍历到与当前元素不相等的元素 m 为止
                while (m < n && nums[i] == nums[m]) {
                    m++;
                    ans++;
                }
                // 不相等
                i = m;
            } else {
                // 当前元素为最后一个元素，需要删去
                ans++;
            }
        }
        // 判断删除后的字符串是否为偶数长度，不是，则要再删除一个元素
        if ((n - ans) % 2 != 0) {
            ans++;
        }
        return ans;
    }
}
